Namespace.Use("Base.Structure", function(ns) {
    function GetLeftIndex(idx) {
        return 2 * idx + 1;
    }

    function GetRightIndex(idx) {
        return 2 * idx + 2;
    }

    function GetParentIndex(idx) {
        return ((idx + 1) >> 1) - 1;
    }

    var MinimumHeap = Polymorphic.Create(
        [Function],
        function(cmp) {
            //
            //  Members.
            //
            var data = [];

            //
            //  Private methods.
            //
            function swap(idx1, idx2) {
                var tmp = data[idx1];
                data[idx1] = data[idx2];
                data[idx2] = tmp;
            }

            function heapify(idx) {
                while(true) {
                    var left = GetLeftIndex(idx);
                    var right = GetRightIndex(idx);
                    var minimum = idx;
                    if (left < data.length && cmp(data[left], data[idx]) < 0) {
                        minimum = left;
                    }
                    if (right < data.length && cmp(data[right], data[minimum]) < 0) {
                        minimum = right;
                    }
                    if (minimum != idx) {
                        swap(minimum, idx);
                        idx = minimum;
                    } else {
                        break;
                    }
                }
            }

            function bubble(idx) {
                while(idx > 0 && cmp(data[idx], data[GetParentIndex(idx)]) < 0) {
                    var parent = GetParentIndex(idx);
                    swap(parent, idx);
                    idx = parent;
                }
            }

            function push(item) {
                var idx = data.length;
                data.push(item);
                bubble(idx);
            }

            function pop() {
                if (data.length == 0) {
                    throw "No item.";
                }
                var first = data[0];
                if (data.length == 1) {
                    data.pop();
                } else {
                    data[0] = data.pop();
                    heapify(0);
                }
                return first;
            }

            function top() {
                if (data.length == 0) {
                    throw "No item.";
                }
                return data[0];
            }

            function clear() {
                data = [];
            }

            //
            //  Public methods.
            //
            this.GetLength = function() {
                return data.length;
            };
            this.Push = function() {
                for (var idx = 0; idx < arguments.length; ++idx) {
                    push(arguments[idx]);
                }
            };
            this.Pop = function() {
                return pop();
            };
            this.Top = function() {
                return top();
            };
            this.Clear = function() {
                clear();
            };
        }
    );

    //  Export public APIs / classes.
    Namespace.Export(ns, "MinimumHeap", MinimumHeap);
});
